package org.gpf;

/**
 * 分治
 * @author gaopengfei
 * @date 2015-4-22 下午8:05:44
 */
public class DivideConquer {

	/**
	 * 数组求和——二分递归
	 * @param arr 需要求和的数组
	 * @param start 数组的开始下标
	 * @param end 数组的结束下标
	 * @return
	 */
	private static int getSum(int arr[], int start, int end) {

		if (start == end)     // 处理递归基
			return arr[start];

		int mid = (start + end) >> 1;
		return getSum(arr, start, mid) + getSum(arr, mid + 1, end);

	}
	
	public static void main(String[] args) {
		
		int[] arr = {1,2,3,4};
		System.out.println(getSum(arr, 0, arr.length-1));

	}

}
